package cn.z2huo.algorithm.sort.insert.half;

//折半插入排序，折半寻找指定元素应该插入的位置。
//不同于折半查找（ 寻找array[mid] == demo ），折半插入寻找的插入位置是low

/**
 * <p>折半插入排序，也叫二分插入排序
 * <p>插入排序时，需要寻找元素在正序数组子序列中的位置，使用二分查找该位置
 *
 * @author z2huo
 */
@Deprecated
public class HalfSort {

	public static void main(String[] args) {
		int low,high,mid;
		int demo;
		int[] array = {11,13,2,34,55,9,44,122,32,2,9};
		int flag = 0;
		int flag2 = 0;
		for(int i=1; i<array.length; i++) {
			low = 0;
			high = i-1;
			demo = array[i];
			//寻找指定数所应待在的正确位置，low
			while(low <= high) {
				mid = (low+high)/2;
				if(demo < array[mid]) {
					//当要查找的数比中小时
					high = mid - 1;
					flag ++;
				}else if(demo >= array[mid]) {
					//当要查找的数比中大时
					low = mid + 1;
					flag ++;
				}
			}
			//将low右边的元素向右移动一个位置
			for(int j=i-1; j>=low; j--) {
				array[j+1] = array[j];
				flag2 ++;
			}
			//将指定数插入到low位置
			array[low] = demo;
			//遍历数组
			for(int m=0; m<array.length; m++) {
				System.out.printf("%d ",array[m]);
			}
			System.out.println();
		}	
		
		System.out.println("以下为最终答案！");
		System.out.println("进行了"+flag+"次比较！");
		System.out.println("进行了"+flag2+"次移动！");
		for(int m=0; m<array.length; m++) {
			System.out.printf("%d ",array[m]);
		}
	}
}
